package me.chan.sort;

import me.chan.std.StdRandom;

import static me.chan.util.SortUtil.*;

/**
 * Created by JanGin on 2017/9/11.
 */
public class QuickSort {

    private QuickSort(){}

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;

        int mid = partition(a, lo, hi);
        sort(a, lo, mid - 1);
        sort(a, mid + 1, hi);
    }



    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];

        while ( true ) {
            while (less(a[++i], v)) {
                if (i == hi) break;
            }

            while (less(v, a[--j])) {
                if (j == lo) break;
            }
            if (i >= j) break;

            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }


    public static void main(String[] args) {

        Comparable[] arr = {'E', 'E', 'G', 'M', 'R', 'A', 'C', 'E', 'R', 'T'};

        show(arr);

        sort(arr);

        //sortWithSentinel(arr);

        show(arr);
    }
}
